Context Free Grammar
Q21.
In the context-free grammar below, S is the start symbol, a and b are terminals, and\epsilon denotes the empty string S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon Which of the following strings is NOT generated by the grammar?Q22.
Consider the following statements about the context-free grammer G=\{S\rightarrow SS, S\rightarrow ab, S\rightarrow ba, S\rightarrow \varepsilon \} 1. G is ambiguous 2. G produces all strings with equal number of a's and b's 3. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G?Q24.
Which of the following grammar rules violate the requirements of an operator grammar? P, Q, R are nonterminals, and r,s,t are terminals. (i)P\rightarrow QR (ii)P\rightarrow QsR (iii)P\rightarrow \varepsilon (iv)P\rightarrow QtRrQ26.
Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S\rightarrow aSb|SS|\epsilon Which of the following statements is true?Q27.
Consider the grammar shown below. S \rightarrow C C C \rightarrow cC | d The grammar isQ28.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: If G is a context free grammar and w is a string of length l in L(G), how long is a derivation of w in G, if G is in Chomsky normal form?Q29.
Consider the following decision problems: (P1): Does a given finite state machine accept a given string? (P2): Does a given context free grammar generate an infinite number of strings? Which of the following statements is true?Q30.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: For a context free grammar, FOLLOW(A) is the set of terminals that can appear immediately to the right of non-terminal A in some "sentential" form. We define two sets LFOLLOW(A) and RFOLLOW(A) by replacing the word "sentential" by "left sentential" and "right most sentential" respectively in the definition of FOLLOW (A).